package targetToOffer.thrDay;

/**
 * @author Godc
 * @description
 */
public class FindNumberIn2DArray {
    public static void main(String[] args) {
        FindNumberIn2DArraySolution s = new FindNumberIn2DArraySolution();
        int[][] matrix = new int[][]{
                {1, 4, 7, 11, 15},
                {2, 5, 8, 12, 19},
                {3, 6, 9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
        };
        boolean f = s.findNumberIn2DArray(matrix, 5);
        System.out.println(f);
    }
}
class FindNumberIn2DArraySolution {
    /**
     * 时间最差o(m+n),把所有的行和列都遍历一遍，也就是右上角
     * @param matrix
     * @param target
     * @return
     */
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        // 以左下角的值为根节点
        int i = matrix.length-1;
        int j = 0;
        while(i>=0&&j<matrix[0].length){
            if(matrix[i][j]==target){
                return true;
            }else if(matrix[i][j]>target){
                // 说明在根节点的上侧
                i--;
            }else if(matrix[i][j]<target){
                // 说明在节点的右侧
                j++;
            }
        }
        return false;
    }
}